package com.zxy.leetcode._00000_00099._00030_00039;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/combination-sum/
 *
 * 组合总和
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，
 * 找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的数字可以无限制重复被选取。
 *
 * 说明：
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。 
 *
 * 标签：回溯算法
 */
public class Test00039 {

    public static void main(String[] args) {
        Test00039 test = new Test00039();

        int[] nums1 = {2,3,6,7};
        System.out.println(test.combinationSum(nums1, 7));

        int[] nums2 = {2,3,5};
        System.out.println(test.combinationSum(nums2, 8));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        if (candidates[0] > target) {
            return result;
        }

        backtrack(result, new LinkedList<>(), candidates, target);

        return result;
    }

    private void backtrack(List<List<Integer>> result, LinkedList<Integer> selectNums, int[] allNums, int target) {
        if (sum(selectNums) == target) {
            result.add(new ArrayList<>(selectNums));
            return;
        }

        for (int i=0; i<allNums.length; i++) {
            // 基于升序数组考虑
            if (sum(selectNums) + allNums[i] > target) {
                return;
            }

            // 重复判断
            if (selectNums.size() > 0 && selectNums.get(selectNums.size() - 1) > allNums[i]) {
                continue;
            }

            selectNums.add(allNums[i]);
            backtrack(result, selectNums, allNums, target);
            selectNums.removeLast();
        }
    }

    private int sum(List<Integer> nums) {
        if (nums.size() == 0) {
            return 0;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

}
